Packing A-paths and cycles with modularity constraints
Youngho Yoo (Georgia Institute of Technology)
Abstract: We study the approximate packing-covering duality, also known as the Erdős-Pósa property, of various families of paths and cycles with modularity constraints. Our main tool is a structure theorem for undirected group-labelled graphs refining the flat wall theorem of Robertson and Seymour, and as a first consequence we obtain the Erdős-Pósa property of cycles of length L mod m for any integer L and odd prime power m. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs L and m. With some more work, we also prove the Erdős-Pósa property of A-paths of length 0 mod p for prime p, resolving a recent question of Bruhn and Ulmer and thereby characterizing when A-paths of length L mod m satisfy the Erdős-Pósa property. Joint work with Robin Thomas.
combinatorics
Audience: researchers in the topic
Comments: pw 121323
Series comments: Check scmscomb.github.io/ for more information